package Hot100;

import common.TreeNode;

/**
 * @author zhangmin
 * @create 2022-01-10 10:18
 * 打家劫舍问题：
 * 198. 打家劫舍--两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警
 * 213. 打家劫舍 II--所有的房屋都 围成一圈 ，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警
 * 337. 打家劫舍 III--这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
 */
public class rob337 {

    /**
     * 198. 打家劫舍
     * 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
     * 如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
     * 动态规划，dp[i]表示到达i位置的最大金额,从后向前进行计算
     * */
    public int rob1(int[] nums) {
        int n=nums.length;
        if (n==1) return nums[0];
        int[] dp=new int[n+2];
        for (int i = n-1; i >= 0; i--) {
            dp[i]=Math.max(dp[i+1],dp[i+2]+nums[i]);
        }
        return dp[0];
    }


    /**
     * 213. 打家劫舍 II
     * 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。
     * 同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
     * 计算从0到n-2，以及1到n-1的最大
     * */
    public int rob(int[] nums) {
        if (nums.length==1) return nums[0];
        int n=nums.length;
        return Math.max(robRange(nums,0,n-2),robRange(nums,1,n-1));
    }
    int robRange(int[] nums,int start,int end){
        int[] dp=new int[nums.length+2];
        for (int i = end; i >=start; i--) {
            dp[i]=Math.max(dp[i+1],dp[i+2]+nums[i]);
        }
        return dp[start];
    }

    /**
     * 337. 打家劫舍 III
     * 在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。
     * 这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一
     * 番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
     * 递归，返回一个数组，记录要当前节点和不要当前节点的打劫金额
     * */
    int[] helper(TreeNode root){
        if (root==null) return new int[]{0,0};
        int[] left = helper(root.left);
        int[] right = helper(root.right);
        int do_it=root.val+left[0]+right[0];
        int not_do=Math.max(left[0],left[1])+Math.max(right[0],right[1]);
        return new int[]{not_do,do_it};
    }
    public int rob3(TreeNode root) {
        int[] res = helper(root);
        return Math.max(res[0],res[1]);
    }

}
